package demo.practice.leetcode_offer;

import java.util.LinkedList;
import java.util.List;

public class Offer59_1 {

    public static void main(String[] args) {

        Offer59_1 offer59_1 = new Offer59_1();
        offer59_1.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        //nums= [1,3,-1,-3,5,3,6,7]
        //用List记录窗口 的最大值  的备选 元素
        //第0 个元素加入  List(本身就是从尾部加入list） 0---1
        //第1个元素加入

        if (nums == null || nums.length == 0 || k > nums.length)
            return new int[0];


        LinkedList<Integer> list = new LinkedList<>();
        int[] arr = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {

            while (list.size() > 0 && nums[i] > nums[list.peekLast()]) {
                list.removeLast();  // list.pollLast();方法也可以，因为前面有size判断，不会抛异常
            }

            list.add(i);    //list.addLast(i);

            //不能用list.size()=k+1 来判断排出  ，因为list中记录的是最大备选元素，所以个数比较少
            if (i - k == list.peekFirst())  //头部元素  == i-k  把头部元素仍掉  i已经超过 队列头那么多，那队列头已经过期
                list.removeFirst();


            if (i +1>= k )
                arr[i +1-k] = nums[list.peek()];
        }

        return arr;

    }
}
